﻿// 0804train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>

using namespace std;

/*
 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 输入: s = "abcabcbb"
 输出: 3
 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串
 */

void solve01(string &s)
{
    string oh_str = s;
    
    int left_index = 0;
    unordered_set<char>oh_set;
    int result = 0;
    int str_size = oh_str.size();

    for (int i=0; i<str_size; i++)
    {
        char curr_char = oh_str[i];
        if (!oh_set.count(curr_char))
        {
            oh_set.insert(curr_char);
        }
        else
        {
            while (oh_set.count(curr_char))
            {
                char left_char = oh_str[left_index];
                oh_set.erase(left_char);
                left_index += 1;
                //while
            }
            oh_set.insert(curr_char);
        }
        result = max(result, i - left_index + 1);

        //for------
    }
    cout << result;
    //solve01------
}


/*
 给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，
并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例1
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例2
输入：target = 4, nums = [1,4,4]
输出：1
 */

int solve02(int target, vector<int>&nums)
{
    vector<int>oh_vec = nums;
    vector<int>queue_vec;

    int total_length = 0;
    for (auto&num:oh_vec)
    {
        total_length += num;
    }

    if (total_length<target)
    {
        return 0;
    }


    int sum = 0;
    int vec_size = nums.size();
    int min_length = INT_MAX;
    for (int i=0; i<vec_size; i++)
    {
        int curr_num = oh_vec[i];
        sum += curr_num;

        while ((!queue_vec.empty()) && (sum - queue_vec[0] >= target))
        {
            int front = queue_vec[0];
            queue_vec.erase(queue_vec.begin());
            sum -= front;
        }
        queue_vec.push_back(curr_num);
        int queue_size = queue_vec.size();

        if (sum>=target)
        {
            min_length = min(min_length, queue_size);
        }
        
        //for------
    }

    //for (auto&num:queue_vec)
    //{
    //    cout << num << ' ';
    //}

    return min_length;
    //solve02
}


/*
 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例1
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例2
输入：s = "a", t = "a"
输出："a"

示例3
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

 */

string solve03(string&s, string&t)
{
    string oh_str = s;
    string target_str = t;

    if (oh_str==target_str)
    {
        return oh_str;
    }

    int str_size = oh_str.size();

    vector<int>map_vec(128, 0);
    for (auto&oh_char: target_str)
    {
        //有可能是重复字符
        map_vec[oh_char] += 1;
    }

    //所需的目标字符串数量（找到-1）
    int target_size = target_str.size();
    int target_count = target_size;

    int left_index = 0;
    int right_index = 0;

    int result_index = 0;

    //设置一个不可能达到的大小
    int window_length = str_size + 1;
    while (right_index < str_size)
    {
        char curr_char = oh_str[right_index];

        //>0说明是目标串
        if (map_vec[curr_char]>0)
        {
            target_count -= 1;
        }

        map_vec[curr_char] -= 1;

        //找到全部目标char
        while (target_count == 0)
        {
            //1更新result_index, window_length
            if (right_index-left_index+1<window_length)
            {
                window_length = right_index - left_index + 1;
                result_index = left_index;
            }

            //2判断left_index指向的是否目标串
            //左窗离开目标串，还原target_count
            if (map_vec[oh_str[left_index]]==0)
            {
                target_count += 1;
            }
            //3还原右窗的操作
            map_vec[oh_str[left_index]] += 1;

        	//4收缩左窗
            left_index += 1;
        }

        right_index += 1;
        //while------
    }

    return window_length == str_size + 1 ? "" : oh_str.substr(result_index, window_length);
    //solve03
    //------
}


int main()
{
	{
        //s="bbaa" t="aba"
        string s = "bbaa", t = "aba";
        cout << solve03(s, t);

        return 0;
	}

	{
        //target=15, nums=[5,1,3,5,10,7,4,9,2,8] 2
        //target = 7, nums = [2,3,1,2,4,3] 2
        int target = 7;
        vector<int>nums = { 2,3,1,2,4,3 };

        cout << solve02(target, nums);

        return 0;
	}

    //s = "abcabcbb" 3
    //s = "pwwkew" 3
    string s = "pwwkew";

    solve01(s);
    //main------
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
